// 乘积为正数的最长子数组长度
class Solution {
    public:
        int getMaxLen(vector<int>& nums) {
            // i位置为结尾最长正数。Big
            // i位置为结尾最长负数。Small
            int n = nums.size();
            vector<int> Big(n),Small(n);
            if(nums[0] > 0)
            {
                Big[0] = 1;
                Small[0] = 0;
            }
            else if (nums[0] < 0)
            {
                Big[0] = 0;
                Small[0] = 1;
            }
            else
            {
                Big[0] = Small[0] = 0;
            }
    
            for(int i = 1; i < n; i++)
            {
                if(nums[i] > 0)
                {
                    Small[i] = Small[i-1] == 0 ? 0 : Small[i-1] + 1;
                    Big[i] = Big[i-1] + 1;
                }
                else if(nums[i] < 0)
                {
                    Small[i] = Big[i-1] + 1;
                    Big[i] = Small[i-1] == 0 ? 0 : Small[i-1] + 1;
                }
                else
                {
                    Small[i] = Big[i] = 0; 
                }
            }
            return *std::max_element(Big.begin(),Big.end());
        }
    };
    // 乘积最大子数组
    class Solution {
        public:
            int maxProduct(vector<int>& nums) {
                //dp[i] 表示以i为结尾连续的最大乘机
                int n = nums.size();
                vector<int> Big(n);
                vector<int> Small(n);
                Big[0] = Small[0] = nums[0];
                for(int i = 1; i < n; i++)
                {
                    Big[i] = max(Big[i-1]*nums[i],max(Small[i-1]*nums[i],nums[i]));
                    Small[i] = min(Big[i-1]*nums[i],min(Small[i-1]*nums[i],nums[i]));
                }
                return *std::max_element(Big.begin(),Big.end());
            }
        };


        // 根据二叉树创建字符串
        class Solution {
            public:
                string dfs(TreeNode* root)
                {
                    if(root == nullptr)
                    {
                        return "";
                    }
                    string ret;
                    ret += to_string(root->val);
                    // 先处理左子树
                    if(root->left || root->right)
                        ret += "(" + dfs(root->left) + ")";
                    // 右子树
                    if(root->right)
                        ret += "(" + dfs(root->right) + ")";
            
                    return ret;
                }
                string tree2str(TreeNode* root) {
                    if(root == nullptr) return "";
                    return dfs(root);
                }
            };